Among programming languages which describe programs for controlling data processing by a computer, in languages passing arguments by value, that is, most of procedural languages, a calling procedure (hereinafter, simply referred to as a caller) in a procedure call evaluates the entire arguments prior to the procedure call. This is referred to as an eager evaluation.
The eager evaluation of the arguments has an advantage in that a latency caused by evaluating the arguments can be overlapped with a latency of the procedure call and hidden by executing the argument evaluation in parallel to a computation of the caller itself, i.e., the eager evaluation is capable of reducing the delay substantially. On the contrary, the eager evaluation has a redundancy that arguments which are not actually referred to in a called procedure (hereinafter, simply referred to as a callee) in the procedure call are evaluated. Accordingly, development of a program requires a measure for excluding the redundancy while performing the eager evaluation of the arguments.
In Scheme, although the arguments are passed by value by default, it is also possible to switch to a lazy evaluation by promise. In addition, when creating a program, a programmer inserts appropriate conditions (hereinafter, referred to as evaluation conditions) derived from conditions for actually referring to the arguments of the callee (hereinafter, referred to as reference conditions) into the caller. Thus, it is made possible to perform the eager evaluation appropriately in accordance with whether or not the arguments are referred to by the callee. Then, the programmer himself inserts evaluation conditions into a source code of the caller, thus guarding the procedure call itself.
Furthermore, as a conventionally-used technique of optimizing a program, there is partial dead code elimination. This optimization moves an operation, that computes a value which is referred to only in a part of a subsequent control flow, immediately before an operation referring to the value, and eliminates partial deadness thereof. However, each of the conventional techniques has a problem as described below. A technique using the promise in the Scheme is executed in a system of switching the argument evaluation from the eager evaluation to the lazy evaluation by specifying a “delay” onto the caller and a “force” onto the callee. Therefore, this technique is accompanied with changes of source codes of both of the caller and callee, and is troublesome. Moreover, the evaluation is switched to the lazy evaluation, thus naturally losing the advantage of the eager evaluation, i.e. the latency of the argument evaluation can be hidden by the parallel execution and can be substantially reduced.
Additionally, in programming, the technique of inserting the evaluation conditions into the source code of the caller means that the reference conditions originally aggregated in the callee are distributed to a large number of the callers. Specifically, the evaluation conditions based on the reference conditions must be inserted into the entire callers which call the called procedure. Accordingly, it becomes less easy to change and maintain a program. Moreover, details of the callee are not always laid open. Even if the details are laid open, the reference conditions are not always public functions and public members, which can be called from the caller. Hence, it may be theoretically impossible to insert the evaluation conditions into the source code of the caller.
Meanwhile, although the partial dead code elimination is a strong optimization technique as it is capable of eliminating an arbitrary dead code, a computational complexity thereof is extremely large as in a range from third to fifth powers of the number of operations. Hence, the partial dead code elimination is not suitable for use in such a compiler which performs dynamic compilation during program execution like a JIT (Just In Time) compiler in Java (trademark of Sun Microsystems in U.S.A.).